/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:${USER}
 * Date:${YEAR}-${MONTH}-${DAY}
 * ${TIME}
 */
public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }


    //Definition for singly-linked list.
    class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur=head;
        int n=0;
        while(cur!=null){
            cur=cur.next;
            n++;
        }
        n=n/k;
        ListNode newNode=new ListNode(0);
        ListNode prev=newNode;//头插的前一个
        cur=head;
        for(int i=0;i<n;i++){//n/k*k=n,所以时间复杂度还是O（n）；
            ListNode tmp=cur;//纪录下一次头插的前一个位置
            for(int j=0;j<k;j++){//头插
                ListNode next=cur.next;
                cur.next=prev.next;
                prev.next=cur;
                cur=next;

            }
            prev=tmp;//更换
        }
        prev.next=cur;//续上之前木有接上的
        return newNode.next;
    }
}